import java.util.Arrays;

public class Solution {
    public static void main(String[] args) {
        Solution test = new Solution();

        // int[] nums = new int[]{1,7,4,9,2,5};
        // System.out.println(test.wiggleMaxLength(nums));

        int[] nums = new int[]{1,2,4,3,5,4,7,2};
        // int[] nums = new int[]{5,5,5,5,5};
        System.out.println(test.findNumberOfLIS(nums));
    }

    public int wiggleMaxLength(int[] nums) {
        /**
         * 先按照直觉做题：
         *      首先，这是子序列问题，因此优先考虑使用动规的方式进行解决
         *      其次，考虑到每个相邻元素之差有正数、负数、零这三种状态，因此我们使用两个状态表进行存储状态（零状态无效）
         * 状态表示：
         *      根据经验加题目要求定义状态表示：
         *      f[i]表示以i下标元素为结尾的所有子序列中，此时状态为下降的，最长摆动序列长度
         *      g[i]表示以i下标元素为结尾的所有子序列中，此时状态为上升的，最长摆动序列长度
         * 状态转移方程：
         *      if(nums[j] > nums[i] && g[j] + 1 > f[i]) {
         *          f[i] = g[j] + 1;
         *      }
         *      if(nums[j] < nums[i] && f[i] + 1 > g[i]) {
         *          g[i] = f[i] + 1;
         *      }
         * 初始化：
         *      规定 j >= 0 && j <= i-1
         *      由于单个元素也可视为摆动序列，因此最差情况为1，故使用1填充数组
         * 返回值：
         *      返回两个dp表的最大值
         * */
        // 1 预处理
        int n = nums.length;
        // 2 创建dp表
        int[] f = new int[n];
        int[] g = new int[n];
        // 3 初始化
        Arrays.fill(f, 1);
        Arrays.fill(g, 1);
        // 4 填表
        int maxLength = 1;
        for(int i = 1; i < n; i++) {
            for(int j = i-1; j >= 0; j--) {
               if(nums[j] > nums[i] && g[j] + 1 > f[i]) {
                   f[i] = g[j] + 1;
               }
               if(nums[j] < nums[i] && f[j] + 1 > g[i]) {
                   g[i] = f[j] + 1;
               }
            }
            // - 更新最大值
            if(f[i] > maxLength) maxLength = f[i];
            if(g[i] > maxLength) maxLength = g[i];
        }
        // 5 返回值
        return maxLength;
    }

    public int findNumberOfLIS(int[] nums) {
        /**
         * 最长递增子序列的个数
         * 解题思路：
         *  本题最重要需要解决的问题就是，仅记录长度时，同一长度可能会有多个，如 1,2,4,3,5， 有1235 1245
         *  这个在原状态中无法体现，因此我们我们需要创建两个表，一个记录长度，一个记录最长长度的个数
         * 状态表示：
         *  f[i]表示以i下标元素为结尾的所有子序列中，最长递增子序列的长度
         *  g[i]表示以i下标元素为结尾的所有子序列中，最长递增子序列的个数
         * 状态转移方程：
         *
         * 初始化：
         *  f表全部初始化为1
         *  g表全部初始化为1
         * */
        // 1 预处理
        int n = nums.length;
        // 2 创建dp表
        int[] f = new int[n];
        int[] g = new int[n];
        // 3 初始化
        Arrays.fill(f ,1);
        Arrays.fill(g ,1);
        // 4 填表
        for(int i = 0; i < n; i++) {
            for(int j = i-1; j >= 0; j--) {
                if(nums[i] > nums[j] && f[j] + 1 >= f[i]) {
                    if(f[j] + 1 == f[i]) {
                        g[i] += g[j];
                    } else if(f[j] + 1 > f[i]) {
                        f[i] = f[j] + 1;
                        g[i] = g[j];
                    }
                }
            }
        }
        // 5 返回值
        int maxLength = Arrays.stream(f).max().getAsInt();
        int maxCount = 0;
        for(int i = 0; i < n; i++) {
            if(f[i] == maxLength) {
                maxCount += g[i];
            }
        }
        return maxCount;
    }
}
